/*-------------------------------------------------------------------------
 *
 * sampling.c
 *	  关系块采样例程。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, 加利福尼亚大学董事会
 *
 *
 * IDENTIFICATION
 *	  src/backend/utils/misc/sampling.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include <math.h>

#include "utils/sampling.h"


/*
 * BlockSampler_Init -- 准备进行块号的随机抽样
 *
 * BlockSampler 提供了关系的块级抽样算法
 * 如在 pgsql-hackers 2004-04-02（主题 "Large DB"）中讨论的那样
 * 它从表中的 nblocks 块中随机选择 samplesize 块作为样本。
 * 如果表中的块少于 samplesize 块，则选择所有块。
 *
 * 由于我们提前知道了块的总数，我们可以使用
 * Knuth 3.4.2 中的简单算法 S，而不是 Vitter 的
 * 算法。
 *
 * 返回 BlockSampler_Next 将返回的块数。
 */
BlockNumber BlockSampler_Init(BlockSampler fc_bs, BlockNumber fc_nblocks, int fc_samplesize,
				  uint32 fc_randseed)
{
	fc_bs->N = fc_nblocks;			/* 测量的表大小 */

	/*
	 * 如果我们决定减少 samplesize 对于那些块数少于或不多于
	 * samplesize 块的表，这里是执行的地方。
	 */
	fc_bs->n = fc_samplesize;
	fc_bs->t = 0;					/* 目前扫描的块数 */
	fc_bs->m = 0;					/* 目前选择的块数 */

	sampler_random_init_state(fc_randseed, &fc_bs->randstate);

	return Min(fc_bs->n, fc_bs->N);
}

bool BlockSampler_HasMore(BlockSampler fc_bs)
{
	return (fc_bs->t < fc_bs->N) && (fc_bs->m < fc_bs->n);
}

BlockNumber BlockSampler_Next(BlockSampler fc_bs)
{
	BlockNumber fc_K = fc_bs->N - fc_bs->t;	/* 剩余块数 */
	int			fc_k = fc_bs->n - fc_bs->m;	/* 仍需采样的块数 */
	double		fc_p;				/* 跳过块的概率 */
	double		fc_V;				/* 随机 */

	Assert(BlockSampler_HasMore(fc_bs));	/* 因此 K > 0 且 k > 0 */

	if ((BlockNumber) fc_k >= fc_K)
	{
		/* 需要所有剩余的 */
		fc_bs->m++;
		return fc_bs->t++;
	}

	/*----------
	 * 这段代码与 Knuth 的算法 S 匹配并不明显。
	 * Knuth 说以 1 - k/K 的概率跳过当前块。
	 * 如果我们要跳过，我们应该前进 t（因此减少 K），并且
	 * 对下一个块重复相同的概率测试。这个简单的
	 * 实现因此要求每个块号调用一次 sampler_random_fract()。
	 * 但是我们可以将其减少为每个选定块一次 sampler_random_fract()
	 * 调用，因为每次 while 测试成功时，我们可以将 V 重新解释为在
	 * 0 到 p 范围内的均匀随机数。因此，我们不需要选择新的 V，而只需
	 * 将 p 调整为其以前值的适当比例，并且我们的下一个循环
	 * 进行适当的概率测试。
	 *
	 * 我们最初 K > k > 0。如果循环将 K 减少到等于 k，
	 * 下一个 while 测试必须失败，因为 p 将变成正好零
	 * （我们假设在除法中不会有舍入误差）。
	 * （注意：Knuth 建议使用 "<=" 循环条件，但我们使用 "<" 只是
	 * 为了进一步确保避免舍入误差。）因此 K 不能小于 k，这意味着
	 * 我们无法失败选择足够的块。
	 *----------
	 */
	fc_V = sampler_random_fract(&fc_bs->randstate);
	fc_p = 1.0 - (double) fc_k / (double) fc_K;
	while (fc_V < fc_p)
	{
		/* 跳过 */
		fc_bs->t++;
		fc_K--;					/* 保持 K == N - t */

		/* 调整 p 为减少范围内的新截止点 */
		fc_p *= 1.0 - (double) fc_k / (double) fc_K;
	}

	/* 选择 */
	fc_bs->m++;
	return fc_bs->t++;
}

/*
 * 这两个例程体现了Jeffrey S. Vitter在ACM Trans. Math. Softw. 11, 1
 * (1985年3月)中发表的“带水库的随机抽样”中的算法Z。Vitter用
 * 记录计数S描述了他的算法，用于在处理另一个记录之前跳过的
 * 记录数。它主要基于t计算，t是已读取的记录数。在调用之
 * 间需要的唯一额外状态是W，一个随机状态变量。
 *
 * reservoir_init_selection_state计算初始W值。
 *
 * 考虑到我们已经读取了t条记录（t >= n），reservoir_get_next_S
 * 确定在处理下一个记录之前要跳过的记录数。
 */
void reservoir_init_selection_state(ReservoirState fc_rs, int fc_n)
{
	/*
	 * 水库抽样没有在需要返回可重复结果的地方使用，所以我们可以随机初始化它。
	 */
	sampler_random_init_state(pg_prng_uint32(&pg_global_prng_state),
							  &fc_rs->randstate);

	/* W的初始值（用于第一次应用算法Z时） */
	fc_rs->W = exp(-log(sampler_random_fract(&fc_rs->randstate)) / fc_n);
}

double reservoir_get_next_S(ReservoirState fc_rs, double fc_t, int fc_n)
{
	double		fc_S;

	/* 这里的魔法常数是Vitter论文中的T */
	if (fc_t <= (22.0 * fc_n))
	{
		/* 使用算法X处理记录，直到t足够大 */
		double		fc_V,
					fc_quot;

		fc_V = sampler_random_fract(&fc_rs->randstate);	/* 生成V */
		fc_S = 0;
		fc_t += 1;
		/* 注意：Vitter代码中的“num”始终等于t - n */
		fc_quot = (fc_t - (double) fc_n) / fc_t;
		/* 找到满足(4.1)的最小S */
		while (fc_quot > fc_V)
		{
			fc_S += 1;
			fc_t += 1;
			fc_quot *= (fc_t - (double) fc_n) / fc_t;
		}
	}
	else
	{
		/* 现在应用算法Z */
		double		fc_W = fc_rs->W;
		double		fc_term = fc_t - (double) fc_n + 1;

		for (;;)
		{
			double		fc_numer,
						fc_numer_lim,
						fc_denom;
			double		fc_U,
						fc_X,
						fc_lhs,
						fc_rhs,
						fc_y,
						fc_tmp;

			/* 生成U和X */
			fc_U = sampler_random_fract(&fc_rs->randstate);
			fc_X = fc_t * (fc_W - 1.0);
			fc_S = floor(fc_X);		/* S暂时设置为floor(X) */
			/* 按照(6.3)的方式测试U <= h(S)/cg(X) */
			fc_tmp = (fc_t + 1) / fc_term;
			fc_lhs = exp(log(((fc_U * fc_tmp * fc_tmp) * (fc_term + fc_S)) / (fc_t + fc_X)) / fc_n);
			fc_rhs = (((fc_t + fc_X) / (fc_term + fc_S)) * fc_term) / fc_t;
			if (fc_lhs <= fc_rhs)
			{
				fc_W = fc_rhs / fc_lhs;
				break;
			}
			/* 测试U <= f(S)/cg(X) */
			fc_y = (((fc_U * (fc_t + 1)) / fc_term) * (fc_t + fc_S + 1)) / (fc_t + fc_X);
			if ((double) fc_n < fc_S)
			{
				fc_denom = fc_t;
				fc_numer_lim = fc_term + fc_S;
			}
			else
			{
				fc_denom = fc_t - (double) fc_n + fc_S;
				fc_numer_lim = fc_t + 1;
			}
			for (fc_numer = fc_t + fc_S; fc_numer >= fc_numer_lim; fc_numer -= 1)
			{
				fc_y *= fc_numer / fc_denom;
				fc_denom -= 1;
			}
			fc_W = exp(-log(sampler_random_fract(&fc_rs->randstate)) / fc_n);	/* 提前生成W */
			if (exp(log(fc_y) / fc_n) <= (fc_t + fc_X) / fc_t)
				break;
		}
		fc_rs->W = fc_W;
	}
	return fc_S;
}


/*----------
 * 采样使用的随机数生成器
 *----------
 */
void sampler_random_init_state(uint32 fc_seed, pg_prng_state *fc_randstate)
{
	pg_prng_seed(fc_randstate, (uint64) fc_seed);
}

/* 在(0 - 1)中均匀分布选择一个随机值R */
double sampler_random_fract(pg_prng_state *fc_randstate)
{
	double		fc_res;

	/* pg_prng_double返回一个[0.0 - 1.0)中的值，因此我们必须拒绝0.0 */
	do
	{
		fc_res = pg_prng_double(fc_randstate);
	} while (unlikely(fc_res == 0.0));
	return fc_res;
}


/*
 * 向后兼容的块采样API
 *
 * 这段代码现在已经废弃，但由于许多FDWs仍在使用它，
 * 至少我们应该保留一段时间。其功能与sampler_random_fract/
 * reservoir_init_selection_state/reservoir_get_next_S相同，
 * 只是所有调用者之间使用了一个公共随机状态。
 */
static ReservoirStateData oldrs;
static bool oldrs_initialized = false;

double anl_random_fract(void)
{
	/* 如果第一次通过则初始化 */
	if (unlikely(!oldrs_initialized))
	{
		sampler_random_init_state(pg_prng_uint32(&pg_global_prng_state),
								  &oldrs.randstate);
		oldrs_initialized = true;
	}

	/* 并计算一个随机分数 */
	return sampler_random_fract(&oldrs.randstate);
}

double anl_init_selection_state(int fc_n)
{
	/* 如果第一次通过则初始化 */
	if (unlikely(!oldrs_initialized))
	{
		sampler_random_init_state(pg_prng_uint32(&pg_global_prng_state),
								  &oldrs.randstate);
		oldrs_initialized = true;
	}

	/* W的初始值（用于第一次应用算法Z时） */
	return exp(-log(sampler_random_fract(&oldrs.randstate)) / fc_n);
}

double anl_get_next_S(double fc_t, int fc_n, double *fc_stateptr)
{
	double		fc_result;

	oldrs.W = *fc_stateptr;
	fc_result = reservoir_get_next_S(&oldrs, fc_t, fc_n);
	*fc_stateptr = oldrs.W;
	return fc_result;
}
